/*
 * @lc app=leetcode.cn id=2170 lang=typescript
 *
 * [2170] 使数组变成交替数组的最少操作数
 */

// @lc code=start

interface NumStatus {
  num: number;
  count: number;
}

function minimumOperations(nums: number[]): number {
  const n = nums.length;
  if (n === 1) return 0;
  // 计算偶数位和奇数位最多和次多出现的数字和次数
  const getMaxNum = (p: number, z1: NumStatus, z2: NumStatus) => {
    const hash = new Map<number, number>();
    for (let i = p; i < n; i += 2) {
      hash.set(nums[i], (hash.get(nums[i]) ?? 0) + 1);
    }
    for (const [num, count] of hash) {
      if (count > z1.count) {
        z2.num = z1.num;
        z2.count = z1.count;
        z1.num = num;
        z1.count = count;
      } else if (count > z2.count) {
        z2.num = num;
        z2.count = count;
      }
    }
  };

  // 出现最多次数的偶数位的值和数量
  const x1: NumStatus = { num: 0, count: 0 };
  // 出现次多次数的偶数位的值和数量
  const x2: NumStatus = { num: 0, count: 0 };
  // 出现最多次数的奇数位的值和数量
  const y1: NumStatus = { num: 0, count: 0 };
  // 出现次多次数的奇数位的值和数量
  const y2: NumStatus = { num: 0, count: 0 };

  getMaxNum(0, x1, x2);
  getMaxNum(1, y1, y2);
  // 共有多少个偶数位
  let n0 = ((n + 1) / 2) | 0;
  // 共有多少个奇数位
  let n1 = n - n0;

  // (偶数位 - 偶数为出现最多次的数字的次数) + (奇数位 - 奇数为出现最多次的数字的次数)
  if (x1.num !== y1.num) return n0 - x1.count + (n1 - y1.count);
  // 如果偶数位和奇数位出现最多次的数字相同，那么就在出现次多的组合中取最小的变化次数
  return Math.min(n0 - x1.count + (n1 - y2.count), n0 - x2.count + (n1 - y1.count));
}
// @lc code=end
